package com.zq.solution.algorithm.sort;

/**
 * @ClassName QuickSort
 * @Description 快速排序
 * @Author ZQ
 * @Date 2020/11/6 11:22
 * @Version V1.0
 **/
public class QuickSort {
    public static int[] quickSort(int[] arr){
        return quickSort(arr,0,arr.length - 1);
    }
    public static int[] quickSort(int[] arr,int low, int high){
        if (low > high) return arr;
        int i = low, j = high, tmp = arr[low];//i左哨兵，j右烧饼，tmp交换基准

        while (i < j){
            while (tmp <= arr[j] && i < j) j--;//右边找一个比tmp小的
            while (tmp >= arr[i] && i < j) i++;//左边找一个比tmp大的
            if (i < j){//交换
                int t = arr[i];
                arr[i] = arr[j];
                arr[j] = t;
            }
        }
        arr[low] = arr[i];//基准值更换为i=j时候的值
        arr[i] = tmp;//将基准值放在中间，满足其左边的都比他小，右边的都比他大
        arr = quickSort(arr,low,i - 1);//递归处理左边排序
        arr = quickSort(arr,i + 1,high);//递归处理右边排序

        return arr;
    }

    public static void main(String[] args) {
        int[] a = new int[]{6,71,72,8,73,75,14,80,18,83,20,87,24,25,27,93,29,97,99,100,37,102,103,42,107,47,112};
        for (Integer n : quickSort(a)){
            System.out.print(n + ",");
        }
    }
}
